package _back_tracking

import org.junit.Assert
import org.junit.Test

/**
 *
 * 1239. 串联字符串的最大长度
 *
 * https://leetcode.cn/problems/maximum-length-of-a-concatenated-string-with-unique-characters/description
 *
 * ```
 * 1239. 串联字符串的最大长度
 * 给定一个字符串数组 arr，字符串 s 是将 arr 的含有 不同字母 的 子序列 字符串 连接 所得的字符串。
 * 请返回所有可行解 s 中最长长度。
 * 子序列 是一种可以从另一个数组派生而来的数组，通过删除某些元素或不删除元素而不改变其余元素的顺序。
 *
 *
 * 示例 1：
 * 输入：arr = ["un","iq","ue"]
 * 输出：4
 * 解释：所有可能的串联组合是：
 * - ""
 * - "un"
 * - "iq"
 * - "ue"
 * - "uniq" ("un" + "iq")
 * - "ique" ("iq" + "ue")
 * 最大长度为 4。
 *
 * 示例 2：
 * 输入：arr = ["cha","r","act","ers"]
 * 输出：6
 * 解释：可能的解答有 "chaers" 和 "acters"。
 *
 * 示例 3：
 * 输入：arr = ["abcdefghijklmnopqrstuvwxyz"]
 * 输出：26
 *
 * 示例 4：
 * 输入：arr = ["aa","bb"]
 * 输出：0
 *
 *
 * 示例 5：
 * 输入：["zog","nvwsuikgndmfexxgjtkb","nxko"]
 * 输出：4
 *
 * 示例 6:
 * 输入：["yy","bkhwmpbiisbldzknpm"]
 * 输出：0
 *
 * ```
 */
class leetcode_1239 {
    @Test
    fun test_1() {
        val result = maxLength(arrayListOf("un", "iq", "ue"))
        val expected = 4
        Assert.assertEquals(expected, result)
    }

    @Test
    fun test_2() {
        val result = maxLength(arrayListOf("cha", "r", "act", "ers"))
        val expected = 6
        Assert.assertEquals(expected, result)
    }

    @Test
    fun test_3() {
        val result = maxLength(arrayListOf("abcdefghijklmnopqrstuvwxyz"))
        val expected = 26
        Assert.assertEquals(expected, result)
    }

    @Test
    fun test_4() {
        val result = maxLength(arrayListOf("aa", "bb"))
        val expected = 0
        Assert.assertEquals(expected, result)
    }

    @Test
    fun test_5() {
        val result = maxLength(arrayListOf("zog", "nvwsuikgndmfexxgjtkb", "nxko"))
        val expected = 4
        Assert.assertEquals(expected, result)
    }

    @Test
    fun test_6() {
        val result = maxLength(arrayListOf("yy", "bkhwmpbiisbldzknpm"))
        val expected = 0
        Assert.assertEquals(expected, result)
    }

    /**
    回溯：子集
    思路：
    1 先过滤掉本身有重复字符的字符串
    2 求子集 : 若字符串中字符在 path 中存在，则不收集该字符串
     */
    fun maxLength(arr: List<String>): Int {
        // TODO:1 先过滤掉本身有重复字符的字符串:比如aa, bb
        val arr: List<String> = arr.filter {
            it.toSet().size == it.length
//            it.toHashSet().size == it.length
        }
        collect(arr, 0, "")
        return len
    }

    private var len: Int = 0
    fun collect(arr: List<String>, start: Int, path: String) {
        // 不同字母？最大长度
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        if (start > arr.size) {
            return
        }
        //收集结果
        if (path.length > len) {
            len = path.length
        }
        // 3 确定单层递归的处理逻辑
        for (i in start until arr.size) {
            // 处理节点
            // 不同字母？
            if (isSameAlpha(arr[i], path)) {
                continue
            }

            // 递归
            collect(arr, i + 1, path + arr[i])

            // 回溯
        }
    }

    private fun isSameAlpha(next: String, path: String): Boolean {
        for (ch in next) {
            if (path.contains(ch)) {
                return true
            }
        }
        return false
    }
}